1. Field of the Invention
This invention relates generally to electronic media storage and retrieval, and in particular, to the storage and retrieval of large amounts of data contained within magnetic tape cartridges. More specifically, the invention relates to an improved method and apparatus for motion optimization in the storage and retrieval of magnetic tape cartridges.
2. Description of the Related Art
In recent years, one method of electronic data storage has been the use of four-by-five inch, 200 megabyte tape cartridges. In the past, the storage and retrieval of such cartridges was for the most part carried out by human operators. Such human intervention not only decreased the reliability of tape selection and replacement, but also prolonged the time between when a data request was made and when that data was retrieved by loading a specific cartridge into an available tape drive.
Recent improvements have resulted in systems utilizing tape cartridges that incorporate magazine type automatic loaders which reduce the time that jobs wait for cartridges to be mounted and subsequently read. An example of an automated cartridge system (ACS) is taught by U.S. Pat. Nos. 4,945,429, 4,928,245, 4,932,826 and 4,864,511, all assigned to the Storage Technology Corporation, which are incorporated by reference herein.
FIG. 1 illustrates one such automated cartridge system. The automated cartridge system is made up of at least one library controller 121 (sometimes referred to as a library management unit or (LMU)) and a plurality of library storage modules (LSMs) 111, 112.
Each library controller 121 provides the interface between a host computer 101, 102 and the LSMs 111, 112. The library controller 121 interprets cartridge motion requests from the host computer 101, 102, relaying instructions to the appropriate LSMs 111, 112.
FIGS. 2-4 illustrate the top view and side view of an LSM 111, 112. Each LSM 111, 112 contains a plurality of storage cells 202 to store magnetic tape cartridges and a robot arm assembly 230 for handling the magnetic tape cartridges. The robot arm assembly 230 comprises a plurality of mechanisms all operating in conjunction to provide a movable arm 321 for retrieving tape cartridges from and returning tape cartridges to their individual storage cells 202. The robot arm 321 includes one or more hand assemblies 240 which performs the actual tape retrieval from, or replacement to, the individual storage cells 202.
Tape cartridges retrieved from the individual storage cells 202 are typically loaded onto tape drives 141, 142, 143, 144 so that the data contained on the tape cartridge can be read by the host computer 101, 102. One or more tape drives 141, 142, 143, 144 are attached to each of the LSMs 111,112. The robot arm 321 loads a tape cartridge into the tape drive 141, 142, 143, 144 with the same motion as the replacement of a tape cartridge into one of the individual storage cells 202.
As illustrated in FIG. 5, tape cartridges are entered into and ejected from LSMs 111, 112 through the use of cartridge access ports (CAP) 160.
Tape cartridges may be transferred under robotic control from one LSM 111 to another LSM 112 through devices called "pass-through-ports" (PTPs) 150. Illustrated in FIG. 6, a PTP 150 is comprised generally of a plurality of storage cells 151, 152, 153, 154, called "PTP slots", adapted for rotation by a mechanism 155, called a "PTP mechanism", for transference between LSMs 111, 112. Through use of these PTPs 150, load sharing is accomplished. Tapes may be transported through PTP slots 151, 152, 153, 154 from one LSM 111 where they might be stored to another LSM 112 where there might be unused tape drives 141, 142, 143, 144. Thus, PTPs 150 allow for a more efficient use of available tape drives 141, 142, 143, 144.
In these systems, the task of transferring a cartridge from one location to another is initiated by a cartridge motion request from the host computer 101, 102 to the library controller 121. When the library controller 121 receives the request, it determines the proper path from the cartridge source to the cartridge destination. This path possibly includes source and/or destination storage cells 202, source and/or destination tape drives 141, 142, 143, 144, source and/or destination CAPs 160, and PTP slots 151, 152, 153, 154 for inter-LSM moves. The library controller 121 "allocates" available resources to cartridge motion requests to accomplish cartridge transfers.
The task of actually transferring a cartridge from one location within an LSM 111, 112 to another consists of two operations, a get and a put. In the get operation, the robotic means 230 retrieves the cartridge from a receptacle at a first location. In the put operation, the robotic means 230 moves the cartridge to its destination and inserts it into a receptacle at a second location.
Tape cartridge transfers along a path consist of the following: (1) path allocation; (2) source get; (3) one or more intermediate puts; (4) one or more intermediate gets; (5) destination put; and (6) path deallocation.
Path allocation consists of allocating for the duration of a tape cartridge transfer all PTP slots 151, 152, 153, 154 necessary for inter-LSM moves through the path, the source and/or destination tape drive 141, 142, 143, 144 and the source and/or destination CAPs 160. If the source tape drive 141, 142, 143, 144 or the source and/or destination CAP 160 are unavailable, the cartridge motion request is rejected. If any of the necessary PTP slots 151, 152, 153, 154 or tape drives 141, 142, 143, 144 are unavailable, the cartridge motion request, as described later, waits on a queue until said slot 151, 152, 153, 154 becomes available.
A source get consists of allocating the arm 321 and hand 240 of the robot mechanism 230 within the source LSM 111, 112 to retrieve a tape cartridge from the source location, whether it be a storage cell 202, tape transport 141, 142, 143, 144 or CAP 160. After the tape cartridge has been retrieved, the arm 321 is deallocated and is free to service other requests. However, the hand 240 remains allocated to the present request.
Intermediate puts and gets are repeated for intermediate LSMs 111, 112 along the selected path. An intermediate put always follows either a source get or intermediate get operation and, therefore, will have a hand 240 already allocated to the request. The intermediate put delivers a cartridge to a PTP slot 151, 152, 153, 154 in an LSM 111, 112. The intermediate put consists of a two step process. First, the PTP mechanism 155 in the intermediate LSM 111, 112 is allocated to the request to receive a cartridge and, second, the arm mechanism 321 within the intermediate LSM 111, 112 is allocated to move the cartridge to and insert it into the PTP slot 151, 152, 153, 154 in that LSM 111, 112. The arm 321, hand 240 and PTP mechanism 155 are deallocated upon completion of the intermediate put.
The intermediate get retrieves a cartridge from a PTP slot 151, 152, 153, 154. The intermediate get consists of a three step process. First, a hand 240 in the intermediate LSM 111, 112 is allocated to the request to retrieve the cartridge from a PTP slot 151, 152, 153, 154. Second, the PTP mechanism 155 is allocated to position the PTP slot 151, 152, 153, 154 in the intermediate PTP 150 for transference of the cartridge. Finally, the arm mechanism 321 within the intermediate LSM 111, 112 is allocated to retrieve a cartridge from the PTP slot 151, 152, 153, 154. The arm 321 and PTP mechanism 155 are deallocated upon completion of the intermediate get. The hand 240 remains allocated to the request.
Destination puts are similar to intermediate puts in that they always follow either a source get or intermediate get operation and, therefore, will have a hand 240 already allocated to the request. The destination put consists of allocating an arm mechanism 321 within the destination LSM 111, 112 to move a cartridge to and insert it into the destination storage cell 202, tape drive 141, 142, 143, 144 or CAP 160. Upon completion of the destination put, the arm 321 and hand 240 allocated to the request are deallocated.
When the tape cartridge has reached its destination location, all PTP slots 151, 152, 153, 154 for inter-LSM moves through the path, the source and/or destination tape drives 141, 142, 143, 144 and the source and/or destination CAPs 160 are deallocated.
As described above, the library controller 121 allocates available resources to cartridge motion requests to accomplish cartridge transfers. However, because the library controller 121 may be asked to execute a plurality of cartridge motion requests at any one time, cartridge motion requests compete for available resources. The library controller 121 manages the competition for available resources by allocating the available resources to the cartridge motion requests on a first-come first-served basis. Cartridge motion requests that request resources first are granted them first. A plurality of queues are implemented to handle the allocation of available resources: a PTP slot queue, a PTP mechanism queue, a drive queue, a hand queue and an arm queue.
If the source location and the destination location are in different LSMs 111, 112, the library controller 121 determines if the necessary PTP slots 151, 152, 153, 154 are available. If the necessary PTP slots 151, 152, 153, 154 are available, the PTP slots 151, 152, 153, 154 are allocated to the request and the path for that particular request is granted, i.e., path allocation. Otherwise, the cartridge motion request is queued on the end of the PTP slot queue, implemented in the library controller's 121 computer memory.
When a new cartridge request is received, it is examined to determine if its destination is a tape drive 141, 142, 143, 144 and, if so, if the destination tape drive 141, 142, 143, 144 is available. If the destination tape drive 141, 142, 143, 144 is available, the drive is allocated to the request and processing of the request continues. If the drive is not available, the request is placed in a drive queue. The library controller 121 determines if a tape drive 141, 142, 143, 144 has become available. If a drive becomes available, the library controller 121 scans the drive queue from the oldest entry to the newest entry to determine if any requests in the drive queue need the available tape drive 141, 142, 143, 144. The available tape drive 141, 142, 143, 144 is allocated to the first request in the queue waiting on that tape drive 141, 142, 143, 144.
Each time a PTP slot 151, 152, 153, 154 becomes available, the PTP slot queue is scanned from the oldest entry to the newest entry to determine which cartridge motion requests in the queue are waiting on that PTP slot 151, 152, 153, 154. The first request found for which all necessary PTP slots 151, 152, 153, 154 are available is granted the path and the necessary PTP slots 151, 152, 153, 154 are allocated to it, i.e., path allocation.
Once a path has been allocated to the cartridge motion request, the tape cartridge is transferred along the granted path through a succession of gets (i.e., a source get and a series of intermediate gets) and puts (i.e., a series of intermediate puts and a destination put).
The allocation of available resources to complete a get is as follows. The cartridge motion request is entered into the hand queue, organized from the oldest entry to the newest, to wait until a hand 240 becomes available. When a hand 240 becomes available, the hand queue is scanned from the oldest entry to the newest entry to determine which request in the queue is waiting on the available hand 240. The available hand 240 is allocated to the first request in the hand queue needing that hand 240. If a transfer between LSMs 111, 112 is involved, the cartridge motion request is entered into the PTP mechanism queue, organized from the oldest entry to the newest, to wait until a PTP mechanism 155 becomes available. When a PTP mechanism 155 becomes available, the PTP mechanism queue is scanned from the oldest entry to the newest entry to determine which request in the queue is waiting on the available PTP mechanism 155. The available PTP mechanism 155 is allocated to the first request in the PTP mechanism queue needing that hand 240. The request is then entered into an arm queue to wait until an arm 321 becomes available. When an arm 321 becomes available the arm queue is scanned from the oldest entry to the newest entry to determine which request in the arm queue is waiting on the available arm 321. The available arm 321 is assigned to the first request in the arm queue needing that arm 321. The request is then satisfied by moving the robotic arm 321 so as to move the hand 240 to the location of the receptacle containing the cartridge that is sought and then using the hand 240 to remove the cartridge from that receptacle.
At this point the get is complete. The arm 321 and PTP mechanism 155 are released for reallocation to the next request in the arm queue needing that arm 321 and the next request in the PTP mechanism queue needing that PTP mechanism 155. The hand 240 retains the cartridge it has retrieved and accordingly cannot be released. The request is then returned to the back of the arm queue to wait for an available arm so it that it can complete its transfer through a put operation.
The put operation is essentially the same as that described in the previous paragraph. Upon completion of the get, the request is returned to the arm queue and, if necessary, the PTP mechanism queue, each queue being organized from the oldest entry to the newest, to wait until an arm 321 and PTP mechanism 155 necessary for the put become available. When a PTP mechanism 155 becomes available, the PTP mechanism queue is scanned from the oldest entry to the newest entry to determine which request in the queue is waiting on the available PTP mechanism 155. The available PTP mechanism is allocated to the first request in the PTP mechanism queue needing that hand 240. When an arm 321 becomes available, the arm queue is scanned from the oldest entry to the newest entry to determine which request in the queue is waiting on the available arm 321. The available arm 321 is allocated to the first request in the arm queue needing that arm 321. When an arm 321 is allocated to the request, the arm 321 is moved so as to move the hand 240 and the cartridge contained therein to the receptacle at the destination location. The hand 240 then inserts the cartridge into the receptacle whereupon the put is complete. The PTP mechanism 155, arm mechanism 321 and hand 240 are then released for reallocation to the next request in the PTP mechanism queue, arm queue and hand queue, respectively.
In the operations described above, there exists one resource queue for each resource, i.e., PTP mechanism 155, drive, hand 240 and arm 321, for the entire automatic cartridge system. Each time a resource becomes available, the appropriate queue is scanned from the oldest entry to the newest entry to determine which request in the queue is waiting on the available resource.
In an alternative implementation, there exists one resource queue for each resource for each LSM 111, 112 in the automated cartridge system. Each time a resource become available in an LSM 111, 112, it is allocated to the first element on the queue (in a first-come, first serve implementation, the first entry on the queue will always be the oldest request). This implementation eliminates the need to scan the queue to determine which request in the queue is waiting on the available resource.
As mentioned above, these automated cartridge systems, cartridge requests are performed only on a first-come first-served basis. That is, all cartridge requests are forced to compete for the available resources on an equal footing, and those that request the resources first are granted them first.
In the copending application of Munro et al., entitled "Task Prioritization For a Tape Storage System," filed simultaneously with the present application, the disclosure of which is herein incorporated by reference, the additional feature of task prioritization for use in an automated cartridge system is disclosed. In accordance with this related art, requests to transfer cartridges may be assigned a priority relating to the urgency of the request. The library controller 121 will recognize these assigned priorities and organize the requests so that higher priority requests are executed ahead of lower priority requests. Moreover, the library controller 121 will increase the priorities of lower priority requests as they remain in the queue to assure that they are eventually executed.
While the above described tape storage system operates as described to store and retrieve data, experience has shown that its performance could be improved. Once the cartridge requests have been received, the ACS is unable to determine, given the requests and the state of the arm 321 and hands 240, what sequence of moves (gets or puts) will execute in the shortest amount of time. The ACS is unable to reorder the sequence of motions necessary to service the requests to minimize the time taken to process these requests.
Therefore, there is a need to better utilize LSM 111, 112 resources by minimizing the time taken to execute a series of motions, that is the gets and puts of each request, by reordering the series.